package everyday;

/**
 * @author zhangmin
 * @create 2022-05-04 13:00
 * 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
 * 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 
 *
 * 思路：
 * 并查集，先处理==的部分，然后再处理！=，如果！=有破坏之前的联通关系，则就是false
 */
public class equationsPossible990 {
    class UF{
        int[] parent;
        public UF(int n){
            parent=new int[n];
            for (int i = 0; i < n; i++) {
                parent[i]=i;
            }
        }
        public int find(int x){
            while (parent[x]!=x){
                //路径压缩
                parent[x]=parent[parent[x]];
                x=parent[x];
            }
            return x;
        }
        public void Union(int p,int q){
            int rootp = find(p);
            int rootq = find(q);
            if (rootp==rootq){
                return;
            }
            parent[rootp]=rootq;
        }
        public boolean isConnected(int p,int q){
            int rootp = find(p);
            int rootq = find(q);
            return rootp==rootq;
        }
    }
    public boolean equationsPossible(String[] equations) {
        int n=equations.length;
        UF uf=new UF(26);
        for (String equation:equations) {
            if (equation.charAt(1)=='='){
                int p = equation.charAt(0) - 'a';
                int q = equation.charAt(3) - 'a';
                uf.Union(p, q);
            }
        }
        //检查不等号关系
        for (String equation: equations) {
            if (equation.charAt(1)=='!'){
                int p = equation.charAt(0) - 'a';
                int q = equation.charAt(3) - 'a';
                if (uf.isConnected(p,q)) return false;
            }
        }
        return true;
    }
}
